package com.shiguiwu.springmybatis.algorithm.sort;

import java.util.Arrays;

/**
 * @description: 快速排序
 * @author: stone
 * @date: Created by 2021/3/25 22:26
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.algorithm.sort
 */
public class QuickSort extends AbstractSort implements Sort{


    public static void main1(String[] args) {
        int[] init = SortTests.init(10);
        System.out.println(Arrays.toString(init));
//        sort(init, 0, init.length - 1);
        QuickSort a = new QuickSort(init);
        a.sort();
//        quickSort(init, 0, init.length - 1);
        System.out.println(Arrays.toString(init));

    }

    public QuickSort(int[] array) {
        super(array);
    }

    /**
     * 快速排序
     */
    @Override
    public void sort() {
        this.sort(array, 0, array.length - 1);
    }

    private void sort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        //定义个标注数
        int stard = array[start];
        int low = start;
        int high = end;
        while (low < high) {
            //右边的数比标注数大
            while (stard <= array[high] && low < high) {
                high--;
            }
            //使用左边的数替换调右边的数
            array[low] = array[high];

            //左边的数比标注数小
            while (low < high && stard >= array[low]) {
                low++;
            }
            array[high] = array[low];
        }

        //把标准数赋值给低的所在位置
        array[low] = stard;
        //处理所以的小数
        sort(array, start, low);
        //处理所有的大数
        sort(array, low + 1, end);


    }

    private static   void sort1(int[] array, int start, int end) {
        if (start > end) {
            return;
        }

        int i = start;
        int j = end;
        int center = array[start];
        while (i < j) {

            while (array[j] >= center && i < j) {
                j--;
            }

            while (array[i] <= center && i < j) {
                i++;
            }


            //将两个数互换位置
            if(i < j){
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }

        }

        //将基准数与中间数互换位置
        array[start] = array[i];
        array[i] = center;

        sort1(array, 0, i - 1);
        sort1(array, j + 1, end);
    }

    public  void quickSort(int[] array,int left,int right){
        if(left > right){
            return;
        }
        //设置一个基准数
        int base = array[left];
        int i = left;
        int j = right;
        while ( i != j){
            //从右边往左边找小于基准数的位置
            while (array[j] >= base && i < j){
                j--;
            }
            //从左边往右边找大于基准数的位置
            while (array[i] <= base && i < j){
                i++;
            }
            //将两个数互换位置
            if(i < j){
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        //将基准数与中间数互换位置
        array[left] = array[i];
        array[i] = base;
        //左边进行排序
        quickSort(array,left,i - 1);
        //右边进行排序
        quickSort(array,i + 1, right);

    }

    private void sortV2(int[] array, int left, int right) {
        int l = left;
        int r = right;
        //定义中轴
        int piovt = array[(left + right) / 2];
        int temp = 0;
        while (l < r) {
            //在piovt的左边一直找，只到大于等于piovt才推出
            while (array[l] < piovt) {
                l+=1;
            }

            while (array[r] > piovt) {
                r-=1;
            }

            //到这里来，就说明已经完成遍历了，
            //最多就等于
            if (l >= r) {
                break;
            }

            temp = array[l];
            array[l] = array[r];
            array[r] = temp;
            //r 前移
            if (array[l] == piovt) {
                r-=1;
            }

            // l前移
            if (array[r] == piovt) {
                l+=1;
            }

        }
        if (r == l) {
            r-=1;
            l+=1;
        }
        //向左递归
        if (left < r) {
            sortV2(array, left, r);
        }
        if (right > l) {
            sortV2(array, l, right);
        }
    }



}
